﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/add-without-plus-lcci/
/*
题目描述：
设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。

示例:
输入: a = 1, b = 1
输出: 2 

提示：
a, b 均可能是负数或 0
结果不会溢出 32 位整数
*/

// 方法1——位运算
/*
思路：
二进制只有两个数字1和0，所以一个二进制位的相加最多也就4种情况：
0 + 0 = 0
0 + 1 = 1
1 = 0 = 0
1 + 1 = 01

从此我们可以发现，对于两个整数a和b，设他们的二进制位相同位上的数字分别是x和y，则a和b相加后不论x+y是否产生进位，
该位置上的数字都为x ^ y。而x+y如果产生进位，那进位的数字则为x&y。
那我们在此基础上再计算(0x^y) ^ (x&y0)，不就得到了x + y再进上一位之后的结果了吗。
因此对于整数a和b，我们可以循环的先让a^b产生不进位的结果，在让(a&b) << 1产生进位的结果并让其向左移一位。
然后再将(a&b) << 1赋值给b，下次再让a^b，以成功的进一位。
如此循环下去直到b == 0，最后a就是最终的结果。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int add(int a, int b) {
	size_t next = 0;
	while (b != 0) {
		next = (size_t)((a & b) << 1);
		a = a ^ b;
		b = next;
	}
	return a;
}
// 时间复杂度：O(log(INT_MAX))。
// 空间复杂度；O(1)。

// 递归版本
int add2(int a, int b) {
	if (b == 0) {
		return a;
	}
	return add2(a ^ b, (a & b) << 1);
}

int main() {
	int a = 1;
	int b = 2;
	printf("%d\n", add2(a, b));
	return 0;
}